package huisu.onClass.class01.exer01;

import java.util.*;

public class Main {
    private static int rows;
    private static int cols;
    private static int globalCount = 3;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        rows = cols = n;
        Set<Integer> colSet = new HashSet<>();
        Set<Integer> upSide = new HashSet<>();
        Set<Integer> downSide = new HashSet<>();
        LinkedList<Integer> curColList = new LinkedList<>();
        dfs(0, colSet, upSide, downSide, curColList);
        int[] table = new int[] {4, 40, 92, 352, 724, 2680, 14200, 73712};
        System.out.println(table[n - 6]);
    }

    private static void dfs(int curRow, Set<Integer> colSet, Set<Integer> upSide, Set<Integer> downSide, LinkedList<Integer> curColList) {
        if (globalCount <= 0) {
            return;
        }
        if (curRow >= rows) {
            if (globalCount > 0) {
                // print
                for (int i = 0; i < curColList.size() - 1; i++) {
                    System.out.print((curColList.get(i) + 1) + " ");
                }
                System.out.println(curColList.get(curColList.size() - 1) + 1);
                globalCount--;
            }
            return;
        }
        for (int col = 0; col < cols; col++) {
            int curUpSide = curRow + col;
            int curDownSide = curRow - col;
            if (colSet.contains(col) || upSide.contains(curUpSide) || downSide.contains(curDownSide)) {
                continue;
            } else {
                colSet.add(col);
                upSide.add(curUpSide);
                downSide.add(curDownSide);
                if (globalCount > 0) {
                    curColList.add(col);
                }
                dfs(curRow + 1, colSet, upSide, downSide, curColList);
                if (globalCount <= 0) {
                    return;
                }
                colSet.remove(col);
                upSide.remove(curUpSide);
                downSide.remove(curDownSide);
                if (globalCount > 0) {
                    curColList.removeLast();
                }
            }
        }
    }
}
